package Sort;

/**
 *归并排序
 * @Author zengxianlong
 * @Date 2021/11/16 15:32
 * @Version 1.0
 */
public class MergeSort {
   public static void main(String[] args) {
      int[] arr={1,4,7,8,3,6,9};
      sort(arr,0,arr.length-1);
      print(arr);
      /*merge1(arr);*/
   }

   public static void sort(int[] arr,int left,int right){
      if (left==right){
         return;
      }
      //分成两半
      int mid=left+(right-left)/2;
      //左边排序
      sort(arr,left,mid);
      //右边排序
      sort(arr,mid+1,right);
      //合并
      merge9(arr,left,mid+1,right);

   }

   static void merge1(int[] arr){
      int mid=arr.length/2;
      int[] temp=new int[arr.length];
      int i=0;
      int j=mid+1;
      int k=0;
      while (i<=mid&&j<arr.length){
         temp[k++]=arr[i]<=arr[j]?arr[i++]:arr[j++];
      }
      while (j<=mid){
         temp[k++]=arr[i++];
      }
      while (j<arr.length){
         temp[k++]=arr[j++];
      }
      print(temp);
   }
   static void merge3(int[] arr,int leftPtr,int rightPtr,int rightBound){
      int mid=rightPtr-1;
      int[] temp=new int[rightBound-leftPtr+1];
      int i=leftPtr;
      int j=rightPtr;
      int k=0;
      while (i<=mid&&j<rightBound){
         temp[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];
      }
      while (j<mid){
         temp[k++]=arr[i++];
      }
      while (j<=rightBound){
         temp[k++]=arr[j++];
      }
      for (int m=0;m<arr.length;m++){
         arr[leftPtr+m]=temp[m];
      }

   }
   static void merge7(int[] arr,int leftPtr,int rightPtr,int rightBound){
      int mid=rightPtr-1;
      int[] temp=new int[rightBound-leftPtr+1];
      int i=leftPtr;
      int j=rightPtr;
      int k=0;
      while (i<=mid&&j<=rightBound){ temp[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];}
      while (j<=mid){temp[k++]=arr[i++];}
      while (j<=rightBound){temp[k++]=arr[j++];}
      for (int m=0;m<temp.length;m++){
         arr[m+leftPtr]=arr[m];
      }

   }
   static void merge6(int[] arr,int leftPtr,int rightPtr,int rightBound){
      int mid=rightPtr-1;
      int[] temp=new int[rightBound-leftPtr+1];
      int i=leftPtr;
      int j=rightPtr;
      int k=0;
      while (i<=mid&&j<rightBound){ temp[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];}
      while (j<mid){temp[k++]=arr[i++];}
      while (j<rightBound){arr[k++]=arr[j++];}
      for (int m=0;m<temp.length;m++){
         arr[leftPtr+m]=temp[m];
      }

   }
   static void merge4(int[] arr,int leftPtr,int rightPtr,int rightBound){
      int mid=rightPtr-1;
      int[] temp=new int[rightBound-leftPtr+1];
      int i=leftPtr;
      int j=rightPtr;
      int k=0;
      while (i<=mid&&j<rightBound){ temp[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];}
      while (j<mid){temp[k++]=arr[i++];}
      while (j<rightBound){arr[k++]=arr[j++];}
      for (int m=0;m<temp.length;m++){
         arr[leftPtr+m]=temp[m];
      }
   }
   static void merge8(int[] arr,int leftPtr,int rightPtr,int rightBound){
      int mid=rightPtr-1;
      int[] temp=new int[rightBound-leftPtr+1];
      int i=leftPtr;
      int j=rightPtr;
      int k=0;
      while (i<=mid&&j<=rightBound){
         temp[k++]=arr[i]<=arr[j]?arr[i++]:arr[j++];
      }
      while (j<=mid){temp[k++]=arr[i++];}
      while (j<=rightBound){temp[k++]=arr[j++];}
      for (int m=0;m<temp.length;m++){
         arr[leftPtr+m]=temp[m];
      }
   }
   static void merge2(int[] arr,int leftPtr,int rightPtr,int rightBound){
      int mid=rightPtr-1;
      int[] temp=new int[rightBound-leftPtr+1];
      int i=leftPtr;
      int j=rightPtr;
      int k=0;
      while (i<=mid&&j<=rightBound){ temp[k++]=arr[i]<=arr[j]?arr[i++]:arr[j++];}
      while (j<=mid){
         temp[k++]=arr[i++];
      }
      while (j<=rightBound){
         temp[k++]=arr[j++];
      }
      for (int m=0;m<temp.length;m++){
         arr[leftPtr+m]=temp[m];
      }
   }
   static void merge9(int[] arr,int leftPtr,int rightPtr,int rightBound){
      int mid=rightPtr-1;
      int[] temp=new int[rightBound-leftPtr+1];
      int i=leftPtr;
      int j=rightPtr;
      int k=0;
      while (i<=mid&&j<=rightBound){
         temp[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];
      }
      while (j<=mid){
         temp[k++]=arr[i++];
      }
      while (j<=rightBound){
         temp[k++]=arr[j++];
      }
      for (int m=0;m<temp.length;m++){
         arr[leftPtr+m]=temp[m];
      }
   }
   static void merge(int[] arr,int leftPtr,int rightPtr,int rightBound){
      int mid=rightPtr-1;
      int[] temp=new int[rightBound-leftPtr+1];
      int i=leftPtr;
      int j=rightPtr;
      int k=0;
      while (i<=mid&&j<=rightBound){
         temp[k++]=arr[i]<=arr[j]?arr[i++]:arr[j++];
      }
      while (j<=mid){
         temp[k++]=arr[i++];
      }
      while (j<=rightBound){
         temp[k++]=arr[j++];
      }
      for (int m=0;m<temp.length;m++){
         arr[leftPtr+m]=temp[m];
      }

   }

   static void swap(int[] arr,int i,int j){
      int temp=arr[j];
      arr[j]=arr[i];
      arr[i]=temp;

   }
   static void print(int[] arr){
      for (int i=0;i<arr.length;i++){
         System.out.print(arr[i]+" ");
      }
   }
}
